﻿//2104. 子数组范围和
//给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
//返回 nums 中 所有 子数组范围的 和 。
//子数组是数组中一个连续 非空 的元素序列。


class Solution {
public:
    long long subArrayRanges(vector<int>& nums)
    {
        long long min_sum = 0;

        stack<int> sta;
        nums.push_back(INT_MIN);
        sta.push(-1);
        for (int i = 0; i < nums.size(); i++)
        {
            while (sta.size() > 1 && nums[i] < nums[sta.top()])
            {
                int cur = sta.top();
                sta.pop();
                min_sum += 1L * nums[cur] * (cur - sta.top()) * (i - cur);
            }
            sta.push(i);
        }

        long long max_sum = 0;
        //子数组最大值最小值的差值的和
        stack<int> sta1;
        nums.pop_back();
        nums.push_back(INT_MAX);
        sta1.push(-1);
        for (int i = 0; i < nums.size(); i++)
        {
            while (sta1.size() > 1 && nums[i] > nums[sta1.top()])
            {
                int cur = sta1.top();
                sta1.pop();
                max_sum += 1L * nums[cur] * (cur - sta1.top()) * (i - cur);
            }
            sta1.push(i);
        }
        return max_sum - min_sum;
    }
};